1. Technical Field
The invention is directed to apparatus and methods for starvation load balancing using a global run queue in a multiple run queue system.
2. Description of Related Art
Multiple processor systems are generally known in the art. In a multiple processor system, a process may be shared by a plurality of processors. The process is broken up into threads which may be processed concurrently. However, the threads must be queued for each of the processors of the multiple processor system before they may be executed by a processor.
One known technique for queuing threads to be dispatched by a processor in a multiple processor system is to maintain a single centralized queue, or xe2x80x9crun queue.xe2x80x9d As processors become available, they take the next thread in the queue and process it. The drawback to this approach is that the centralized queue becomes a bottleneck for the threads and processing time may be lost due to processors spinning on a run queue lock, i.e. becoming idle, while waiting to take the next thread from the centralized queue.
Another known technique for queuing threads is to maintain separate queues for each processor. Thus, when a thread is created, it is assigned to a processor in a round robin fashion. With such a technique, some processors may become overloaded while other processors are relatively idle. Furthermore, some low priority threads may become starved, i.e. are not provided with any processing time, because higher priority threads are added to the run queue of the processor for which the low priority threads are waiting.
Thus, there is a need for new technology to provide apparatus and methods for balancing the workload of a multiple processor system while maintaining a high throughput in the multiple processor system. Furthermore, there is a need for new technology to prevent unfair starvation of low priority threads.
The present invention provides apparatus and methods for starvation load balancing by using a global run queue in a multiple run queue system. Starvation load balancing is a method for ensuring fair treatment of low priority threads on a multiple run queue system. Low priority threads may not be serviced for potentially very long periods of time, which may be normal expected behavior for such threads competing on a busy system. However, it is undesirable for similar low priority threads to be treated differently as a side-effect of having multiple run queues. The present invention provides a mechanism to ensure equitable treatment of the low priority threads system-wide.
The apparatus performs initial load balancing, idle load balancing, periodic load balancing and starvation load balancing, to ensure that the workloads for the processors of the system are optimally balanced. Initial load balancing addresses to which run queue a new thread of a process should be assigned. Idle load balancing addresses how to shift threads from one run queue to another when a processor is becoming idle. Periodic load balancing addresses how to shift threads from the heaviest loaded run queue to the lightest loaded run queue in order to maintain a load balance. Starvation load balancing address how to requeue threads that are being starved of processor processing time.
These techniques make use of global and local run queues to perform load balancing. The global run queue is associated with a node of processors which service the global run queue. Each processor within the node also services a local run queue. Thus, each processor in a node services both the global run queue and a local run queue.
Initial load balancing makes use of the global run queue to place threads that are not able to be placed directly in the local run queue of an idle processor. Starvation load balancing makes use of the global run queue to place threads that have been starved for processor time in order to provide a greater likelihood that a less busy processor will dispatch the thread.
Idle load balancing and periodic load balancing attempt to shift threads from one local run queue to another in an effort to balance the workloads of the processors of the system.